package graph.weighted.minimun_spanning_tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

import graph.weighted.CandyWeightedEdge;
import graph.weighted.CandyWeightedGraph;
import graph.weighted.connectedComponent.CandyConnectedComponent;
import unionFound.CandyUnionFind;
import unionFound.CandyUnionFindImpl;
/**
 * 
 * @Title: CandyPrim.java 
 * @Package graph.weighted.minimun_spanning_tree 
 * @Description: 求解最小生成树：prim算法
 * @author CandyWall   
 * @date 2021年1月20日 下午4:22:27 
 * @version V1.0
 */
public class CandyPrim_v1 {
    private CandyWeightedGraph graph; 
    
    public CandyPrim_v1(CandyWeightedGraph graph) {
        this.graph = graph;
    }
    
    /**
     * 获取最小生成树中的所有边
     * @return
     */
    public ArrayList<CandyWeightedEdge> getMst() {
        ArrayList<CandyWeightedEdge> mst = new ArrayList<>();
        CandyConnectedComponent connectedComponent = new CandyConnectedComponent(graph);
        if(connectedComponent.getConnectedComponentCount() > 1) {
            return mst;
        }
        
        // Prim
        boolean[] visited = new boolean[graph.getVertex_num()];
        // 先把顶点0纳入生成树中
        visited[0] = true;
        // 还需要把剩下的graph.getVertext_num()个顶点需要被纳入生成树中
        for(int i = 1; i < graph.getVertex_num(); i++) {
            // 在每一轮循环中找出最短横切边
            // 依次找出纳入了生成树中的顶点，以及跟它们相邻的并且没有纳入到生成树中的顶点
            CandyWeightedEdge minEdge = new CandyWeightedEdge(-1, -1, Integer.MAX_VALUE);
            for(int v = 0; v < graph.getVertex_num(); v++) {
                if(visited[v]) {
                    // 找出跟顶点v相邻，并且没有纳入到生成树中的顶点，这些顶点跟v相连的边中最短的边
                    for(int w : graph.adjacentVertexes(v)) {
                        int weight = graph.getWeight(v, w);
                        if(!visited[w] && weight < minEdge.getWeight()) {
                            minEdge = new CandyWeightedEdge(v, w, weight); 
                        }
                    }
                }
            }
            // 将最短横切边纳入最小生成树
            mst.add(minEdge);
            // 扩充切分
            visited[minEdge.getW()] = true;
        }
        return mst;
    }

    public static void main(String[] args) {
        CandyWeightedGraph graph = new CandyWeightedGraph("testData/weightedGraph/graph.txt");
        CandyPrim_v1 prim = new CandyPrim_v1(graph);
        System.out.println(prim.getMst());
    }
}
